#include <string>
#include <unordered_map>
#include <iostream>
#include <climits>

using namespace std;

class Solution 
{
public:
    string minWindow(string s, string t) 
    {
        if(s.empty() || t.empty() || t.length() > s.length())
        {
            return "";
        }
        unordered_map<char, int> needs;
        for(int i = 0; i < t.length(); i++)
        {
            needs[t[i]]++;
        }
        int required_count = t.length();

        int left = 0;
        int min_len = INT_MAX;
        int result_start = 0;

        for(int right = 0; right < s.length(); right++)
        {
            char char_in = s[right];

            if(needs.find(char_in) != needs.end())
            {
                if(needs[char_in] > 0)
                {
                    required_count--;
                }
                needs[char_in]--;
            }

            while(required_count == 0)
            {
                int current_len = right - left + 1;
                if(current_len < min_len)
                {
                    min_len = current_len;
                    result_start = left;
                }
                char char_out = s[left];
                if(needs.find(char_out) != needs.end())
                {
                    needs[char_out]++;
                    if(needs[char_out] > 0)
                    {
                        required_count++;
                    }
                }
                left++;
            }
        }
        if(min_len == INT_MAX)
        {
            return "";
        }
        else
        {
            return s.substr(result_start, min_len);
        }
    }
};

int main() 
{
    Solution solution;
    
    // 测试案例1: s = "ADOBECODEBANC", t = "ABC"
    cout << "测试案例1:" << endl;
    string s1 = "ADOBECODEBANC";
    string t1 = "ABC";
    cout << "输入: s = \"" << s1 << "\", t = \"" << t1 << "\"" << endl;
    string result1 = solution.minWindow(s1, t1);
    cout << "输出: \"" << result1 << "\"" << endl;
    cout << "期望: \"BANC\"" << endl << endl;
    
    // 测试案例2: s = "a", t = "a"
    cout << "测试案例2:" << endl;
    string s2 = "a";
    string t2 = "a";
    cout << "输入: s = \"" << s2 << "\", t = \"" << t2 << "\"" << endl;
    string result2 = solution.minWindow(s2, t2);
    cout << "输出: \"" << result2 << "\"" << endl;
    cout << "期望: \"a\"" << endl << endl;
    
    // 测试案例3: s = "a", t = "aa"
    cout << "测试案例3:" << endl;
    string s3 = "a";
    string t3 = "aa";
    cout << "输入: s = \"" << s3 << "\", t = \"" << t3 << "\"" << endl;
    string result3 = solution.minWindow(s3, t3);
    cout << "输出: \"" << result3 << "\"" << endl;
    cout << "期望: \"\"" << endl << endl;
    
    // 测试案例4: 无匹配
    cout << "测试案例4 (无匹配):" << endl;
    string s4 = "abc";
    string t4 = "def";
    cout << "输入: s = \"" << s4 << "\", t = \"" << t4 << "\"" << endl;
    string result4 = solution.minWindow(s4, t4);
    cout << "输出: \"" << result4 << "\"" << endl;
    cout << "期望: \"\"" << endl << endl;
    
    // 测试案例5: t长度大于s
    cout << "测试案例5 (t长度大于s):" << endl;
    string s5 = "ab";
    string t5 = "abc";
    cout << "输入: s = \"" << s5 << "\", t = \"" << t5 << "\"" << endl;
    string result5 = solution.minWindow(s5, t5);
    cout << "输出: \"" << result5 << "\"" << endl;
    cout << "期望: \"\"" << endl << endl;
    
    // 测试案例6: 重复字符
    cout << "测试案例6 (重复字符):" << endl;
    string s6 = "ADOBECODEBANC";
    string t6 = "AABC";
    cout << "输入: s = \"" << s6 << "\", t = \"" << t6 << "\"" << endl;
    string result6 = solution.minWindow(s6, t6);
    cout << "输出: \"" << result6 << "\"" << endl;
    cout << "期望: \"ADOBEC\" 或其他包含两个A、一个B、一个C的最短子串" << endl << endl;
    
    // 测试案例7: 整个字符串
    cout << "测试案例7 (整个字符串):" << endl;
    string s7 = "abc";
    string t7 = "cba";
    cout << "输入: s = \"" << s7 << "\", t = \"" << t7 << "\"" << endl;
    string result7 = solution.minWindow(s7, t7);
    cout << "输出: \"" << result7 << "\"" << endl;
    cout << "期望: \"abc\"" << endl << endl;
    
    // 测试案例8: 单字符重复
    cout << "测试案例8 (单字符重复):" << endl;
    string s8 = "aaaa";
    string t8 = "aa";
    cout << "输入: s = \"" << s8 << "\", t = \"" << t8 << "\"" << endl;
    string result8 = solution.minWindow(s8, t8);
    cout << "输出: \"" << result8 << "\"" << endl;
    cout << "期望: \"aa\"" << endl << endl;
    
    // 测试案例9: 复杂情况
    cout << "测试案例9 (复杂情况):" << endl;
    string s9 = "ADOBECODEBANC";
    string t9 = "ABCC";
    cout << "输入: s = \"" << s9 << "\", t = \"" << t9 << "\"" << endl;
    string result9 = solution.minWindow(s9, t9);
    cout << "输出: \"" << result9 << "\"" << endl;
    cout << "期望: \"CODECBANC\" 或其他包含一个A、一个B、两个C的最短子串" << endl << endl;
    
    // 测试案例10: 空字符串
    cout << "测试案例10 (空字符串):" << endl;
    string s10 = "";
    string t10 = "a";
    cout << "输入: s = \"" << s10 << "\", t = \"" << t10 << "\"" << endl;
    string result10 = solution.minWindow(s10, t10);
    cout << "输出: \"" << result10 << "\"" << endl;
    cout << "期望: \"\"" << endl << endl;
    
    // 测试案例11: 大小写敏感
    cout << "测试案例11 (大小写敏感):" << endl;
    string s11 = "AaBbCc";
    string t11 = "abc";
    cout << "输入: s = \"" << s11 << "\", t = \"" << t11 << "\"" << endl;
    string result11 = solution.minWindow(s11, t11);
    cout << "输出: \"" << result11 << "\"" << endl;
    cout << "期望: \"BbCc\" 或其他包含a、b、c的最短子串" << endl << endl;
    
    return 0;
}